Verify preorder sequence in binary search tree [BST]

Time: O(N); Space: O(1); medium

Given an array of numbers, verify whether it is the correct preorder traversal sequence of a Binary Search Tree.

You may assume each number in the sequence is unique.

Example 1:

    5
   / \
  2   6
 / \
1   3

Input: [5,2,6,1,3]

Output: False

Example 2:

    5
   / \
  2   1
 / \
3   6

Input: [5,2,1,3,6]

Output: True

Follow up:

  1. Could you do it using only constant space complexity?

[5]:

class Solution1(object):
    """
    Time: O(N)
    Space: O(1)
    """
    def verifyPreorder(self, preorder):
        '''
        :type preorder: int
        :rtype: bool
        '''
        low, i = float("-inf"), -1
        for p in preorder:
            if p < low:
                return False
            while i >= 0 and p > preorder[i]:
                low = preorder[i]
                i -= 1
            i += 1
            preorder[i] = p
        return True

[6]:

s = Solution1()
preorder = [5,2,6,1,3]
assert s.verifyPreorder(preorder) == False
preorder = [5,2,1,3,6]
assert s.verifyPreorder(preorder) == True

[7]:

class Solution2(object):
    """
    Time: O(N)
    Space: O(N)
    """
    def verifyPreorder(self, preorder):
        """
        :type preorder: int
        :rtype: bool
        """
        low = float("-inf")
        path = []
        for p in preorder:
            if p < low:
                return False
            while path and p > path[-1]:
                low = path[-1]
                path.pop()
            path.append(p)
        return True

[8]:

s = Solution2()
preorder = [5,2,6,1,3]
assert s.verifyPreorder(preorder) == False
preorder = [5,2,1,3,6]
assert s.verifyPreorder(preorder) == True